\documentclass{ctexart}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{diagbox}

\title{作业六:排序算法类的实现}


\author{夏知人 \\ 信息与计算科学  3210103669}

\begin{document}

\maketitle



\section{课本提供的算法效率比较}
有序度为1$\%$时
\centering
\begin{threeparttable}
\begin{tabular}{|c|c|c|c|c|c|} \hline

\diagbox{测试次数}{算法类型}&heapsort堆排序  &quicksort快速排序\\ \hline
1  &0.297s  &0.201s\\ \hline
2  &0.287s  &0.199s\\ \hline
3  &0.291s  &0.203s\\ \hline
\end{tabular}
\end{threeparttable}

有序度为10$\%$时
\centering
\begin{threeparttable}
\begin{tabular}{|c|c|c|c|c|c|} \hline

\diagbox{测试次数}{算法类型}&heapsort堆排序  &quicksort快速排序\\ \hline
1  &0.688s  &0.211s\\ \hline
2  &0.675s  &0.205s\\ \hline
3  &0.681s  &0.203s\\ \hline
\end{tabular}
\end{threeparttable}

有序度为90$\%$时
\centering
\begin{threeparttable}
\begin{tabular}{|c|c|c|c|c|c|} \hline

\diagbox{测试次数}{算法类型}&heapsort堆排序  &quicksort快速排序\\ \hline
1  &1.988s  &0.165s\\ \hline
2  &1.975s  &0.156s\\ \hline
3  &2.001s  &0.152s\\ \hline
\end{tabular}
\end{threeparttable}

有序度为99$\%$时
\centering
\begin{threeparttable}
\begin{tabular}{|c|c|c|c|c|c|} \hline

\diagbox{测试次数}{算法类型}&heapsort堆排序  &quicksort快速排序\\ \hline
1  &1.998s  &0.158s\\ \hline
2  &2.021s  &0.159s\\ \hline
3  &2.031s  &0.160s\\ \hline
\end{tabular}
\end{threeparttable}


\section{改进后的排序算法效率比较}
有序度为1$\%$时
\centering
\begin{threeparttable}
\begin{tabular}{|c|c|c|c|c|c|} \hline

\diagbox{测试次数}{算法类型}&heapsort堆排序  &quicksort快速排序\\ \hline
1  &0.002s  &0.09s\\ \hline
2  &0.002s  &0.089s\\ \hline
3  &0.002s  &0.088s\\ \hline
\end{tabular}
\end{threeparttable}

有序度为10$\%$时
\centering
\begin{threeparttable}
\begin{tabular}{|c|c|c|c|c|c|} \hline

\diagbox{测试次数}{算法类型}&heapsort堆排序  &quicksort快速排序\\ \hline
1  &0.002s  &0.09s\\ \hline
2  &0.003s  &0.089s\\ \hline
3  &0.002s  &0.088s\\ \hline
\end{tabular}
\end{threeparttable}

有序度为90$\%$时
\centering
\begin{threeparttable}
\begin{tabular}{|c|c|c|c|c|c|} \hline

\diagbox{测试次数}{算法类型}&heapsort堆排序  &quicksort快速排序\\ \hline
1  &0.002s  &0.096s\\ \hline
2  &0.002s  &0.096s\\ \hline
3  &0.002s  &0.095s\\ \hline
\end{tabular}
\end{threeparttable}

有序度为99$\%$时
\centering
\begin{threeparttable}
\begin{tabular}{|c|c|c|c|c|c|} \hline

\diagbox{测试次数}{算法类型}&heapsort堆排序  &quicksort快速排序\\ \hline
1  &0.003s  &0.096s\\ \hline
2  &0.003s  &0.096s\\ \hline
3  &0.002s  &0.113s\\ \hline
\end{tabular}
\end{threeparttable}

\section{设计思路}
快速排序法在有序数据时速度明显慢很多，是由于快速排序法在处理有序数据时，仍需要不断递归二分两组数据，
所以改进的方法就是在快速排序法基准数的选择上，通过不选择左端节点，而是随机选取一个节点，避免处理数据
时数字有序带来的分块无法快速减小的浪费。


\end{document}
